The present invention relates generally to an IC card (integrated circuit card) capable of processing encryption data or information. More particularly, the invention is concerned with a method capable of executing at a high speed elliptic curve encryption processing in an encryption processing in which hardware designed for executing a high-speed algorithm for a residual multiplication arithmetic (multiplication on the set of integers) is adopted and a device such as an IC card in which the above-mentioned method is adopted.
For having better understanding of the present invention, technical background thereof will first be described in some detail. As an encryption scheme for a public key crypto-system, there is known an RSA encryption scheme which was invented by Rivest, Shamir and Adleman in 1978. The basic principle underlying the RSA encryption will be reviewed below.
Basic Principle of RSA Encryption
Representing a secret key by (d, n), a public key by (e, n), a plaintext by M and a co-processor by c, respectively, then the encryption and the decryption can be represented, respectively, by the calculation formulae mentioned below.
Encryption: Cxe2x89xa1Me (mod n), and
decryption: Mxe2x89xa1Cd (mod n).
In the above expressions, n is given by pxc2x7q where p and g represent large prime numbers, respectively which satisfy the conditions that xcex(n)=LCM {(pxe2x88x921), (qxe2x88x921)} (where LCM represents a least common multiple), GCD {e, xcex(n)}=1 (where GCD represents a greatest common divisor), and that d=exe2x88x921 mod xcex(n).
The security of the RSA encryption is ensured by the fact that it is very difficult to factorize n into prime factors. In this conjunction, it is recommended to employ large integers on the order of 1024 bits as the parameters such as e, d, n, M and so forth. In that case, modular multiplication on the set of integers (hereinafter referred to also as the residual multiplication arithmetic) has to be conducted 1534.5 times on an average for a single processing in accordance with the encryption formula Cxe2x89xa1Me (mod n), when such a binary operation method is resorted to, which is described in detail in D. E. Knuth: xe2x80x9cSEMINUMERICAL ALGORITHMS ARITHMETICxe2x80x9d, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1969.
Furthermore, as another encryption scheme belonging to the public key crypto-system, there may be mentioned an elliptic curve encryption processing proposed by Koblitz and Miller independently in 1985. The basic principle underlying this elliptic curve encryption will be reviewed below.
Principle of the Elliptic Curve Encryption
Representing the order of a finite field by a prime number p while representing by a and b the parameters which determine the elliptic curve, a set which includes a set of points capable of satisfying the conditions given by the undermentioned expression and which is added with a virtual point at infinity is referred to as the elliptic curve Ep. For the convenience of illustration, the elliptic curve Ep of concern is presumed to be capable of being represented on the affine coordinate system.
Ep: y2xe2x89xa1x3+ax+b (mod p)
Addition between two points P1 and P2 on the elliptic curve, i.e., P3=P1+P2 (where Pi=(xi, yi)), can be defined as follows:
Case where P1xe2x89xa0P2 
In this case, the arithmetics as involved will hereinafter be referred to as the elliptic addition arithmetic.
The elliptic addition arithmetic includes addition performed zero times, subtraction performed six times, multiplication performed twice and division performed once, as follows:
xcex=(y2xe2x88x92y1)/(x2xe2x88x92x1),
xe2x80x83x3=xcex2xe2x88x92x1xe2x88x92x2,
and
y3=xcex(x1xe2x88x92x3)xe2x88x92y1
Case where P1=P2 
In this case, the arithmetic will hereinafter be referred to as the elliptic by-two-multiplication arithmetic.
The elliptic by-two-multiplication arithmetic includes addition performed once, subtraction performed three times, multiplication performed three times and division performed once, as follows:
xcex=(3xc3x9712+a)/2y1, x3=xcex2xe2x88x922xc3x971
and
y3=xcex(x1xe2x88x92x3)xe2x88x92y1
At this juncture, it should be mentioned that all the arithmetic operations mentioned above are performed on a residue system to modulus p.
The security of the elliptic curve encryption described above is based on the fact that when a point derived through multiplication of a point A on the elliptic curve by x (i.e., the point obtained by adding xe2x80x9cAxe2x80x9d x times) is represented by B(=xxc2x7A), extreme difficulty will be encountered in finding the value of x on the basis of the values of the points A and B if known. This feature is known as the elliptic curve discrete logarithm problem. In order to ensure the security comparable to that realized by the 1024-bit RSA encryption described previously, it is recommended that each of the parameters such as p, a, xi, yi, etc. be an integer on the order of 160 bits.
The arithmetic operation for determining the point (kxc2x7P) corresponding to multiplication of a point P by k, which constitutes one of the basic arithmetic operations for the elliptic curve encryption, can be realized by computation in accordance with the addition on the elliptic curve (elliptic curve addition) mentioned above. In this conjunction, it is noted that the modular division on the set of integers (hereinafter also referred to as the residual division arithmetic) has to be conducted in order to determine xcex. The residual division arithmetic (i.e., modular division on the set of integers) can generally be coped with by resorting to an algorithm such as an extended Euclidean algorithm or the like, which requires, however, lots of processing times. Such being the circumstances, there is widely adopted the method or scheme for realizing the arithmetics on the elliptic curve by transforming a point on a two-dimensional affine coordinate system into a point on a three-dimensional coordinate system without resorting to the residual division arithmetic processing. For more particulars of this scheme, reference may be made to D. V. Chudnovsky and G. V. Chudnovsky: xe2x80x9cSEQUENCES OF NUMBERS GENERATED BY ADDITION IN FORMAL GROUPS AND NEW PRIMALITY AND FACTORIZATION TESTSxe2x80x9d, Advances in Applied Mathematics, Vol. 7, pp. 385-434, 1986. By way of example, when the addition arithmetics on the elliptic curve Ep in the two-dimensional affine coordinate system is transformed into addition arithmetics in the three-dimensional projective coordinate system so that the conditions given by xxe2x89xa1X/Z2 (mod p) and yxe2x89xa1Y/Z3 (mod p) can be satisfied, the addition arithmetics are defined as follows:
The elliptic addition arithmetic includes addition performed twice, subtraction performed five times, multiplication performed sixteen times and division performed zero times, as follows:
X3=R2xe2x88x92TW2,
2Y3=VRxe2x88x92MW3,
and
Z3=Z1Z2W
where
W=X1Z22xe2x88x92X2Z12,
R=Y1Z23xe2x88x92Y2Z13,
T=X1Z22+X2Z12,
M=Y1Z23xe2x88x92Y2Z13,
and
V=TW2xe2x88x922X3.
The elliptic by-two-multiplication arithmetic includes addition performed once, subtraction performed three times, multiplication performed ten times and division performed zero times, as follows:
X3=M2xe2x88x922S,
Y3=M(Sxe2x88x92X3)xe2x88x92T,
and
xe2x80x83Z3=2Y1Z1
where
M=3X12+aZ14,
S=4X1Y12,
and
T=8Y14
At this juncture, it should be mentioned that all the arithmetic operations mentioned above are performed on a residue system to modulus p.
As another example of the coordinate transformation methods, there may be mentioned a coordinate transformation to a three-dimensional homogeneous coordinate system such that the conditions given by the following expressions can be satisfied.
xxe2x89xa1X/Z (mod p),
and
yxe2x89xa1Y/Z (mod p)
At this juncture, it should however be noted that the residual division arithmetic (i.e., division on the set of integers) has to be executed once upon reverse transformation from the three-dimensional coordinate system to the two-dimensional coordinate system.
Assuming, by way of example, that a 160-bit elliptic curve encryption is transformed to that on the three-dimensional projective or mapping coordinate system, and that the kxc2x7P arithmetic is realized by using the binary operation scheme mentioned hereinbefore, the residual multiplication arithmetic will have to be performed as many times as 2862 times on an average.
As will now be appreciated from the foregoing description, in the public key encryption scheme such as the RSA encryption method and the elliptic curve encryption method, lots of residual multiplication arithmetic processings (i.e., modular multiplications on the set of integers) are required as the basic arithmetic operation. Such being the circumstances, there have been developed and proposed methods or schemes for speeding up the residual multiplication arithmetic by resorting to a high-speed algorithm for the residual multiplication arithmetic, to thereby speed up the encryption processing on the whole.
In particular, in the RSA encryption scheme, the arithmetic operations therefor are in large part the residual multiplication arithmetic. Thus, there has been realized such hardware designed for executing the high-speed algorithm for the residual multiplication arithmetic. Further, the IC card capable of executing the RSA encryption processing at a high speed has been realized by employing such hardware so as to meet the stipulation of the IC Card Standards ISO7816.
By contrast, in the case of the elliptic curve encryption scheme, residual four-rules arithmetics are required as the basic arithmetic operations. Among the residual four-rules arithmetics, the residual division arithmetic requires lots of processing time, which presents a serious problem to the approach for speeding up the elliptic curve encryption processing. Parenthetically, a method or scheme for decreasing the number of times the residual division arithmetic has to be executed in the elliptic curve encryption processing and a scheme for speeding up the residual division arithmetic have already been proposed in A. Shimbo: xe2x80x9cAPPLICATION OF MONTGOMERY ARITHMETICS TO ELLIPTIC CURVE ENCRYPTIONxe2x80x9d, SCIS, 1997 (The 1997 Symposium on Cryptography and Information Security). However, it is noted that attempt for applying the methods disclosed in the above literature to the devices such as the IC card stipulated in the Standards ISO7816 will unavoidably limited in view of the present state of the semiconductor technology. Thus, lot of time will be taken for the multiplicative inverse arithmetic operation in the residual division arithmetic, making it difficult to enhance the processing speed.
Accordingly, in the light of the state of the art described above, it is an object of the present invention to provide a method capable of executing at a high speed the elliptic curve encryption processing in an encryption processing in which hardware designed for executing a high-speed algorithm for the residual multiplication arithmetic is adopted.
Another object of the invention is to provide a device such as an IC card in which the above-mentioned method is adopted.
Yet another object of the present invention is to provide a method capable of executing at a high speed the digital signature processing in a device such as, e.g. an IC card, in which hardware designed for executing a high-speed algorithm for the residual multiplication arithmetic (i.e., modular multiplication on the set of integers) is adopted.
Still another object of the invention is to provide a device such as an IC card in which the method mentioned just above is adopted.
It is a further object of the present invention to provide a method capable of speeding up the multiplicative inverse arithmetic in the residual division arithmetic (i.e., modular division on the set of integers) in the elliptic curve encryption processing.
It is also an object of the present invention to provide a device in which the method mentioned just above is adopted.
In view of the above and other objects which will become apparent as the description proceeds, there are provided according to aspects of the present invention undermentioned scheme or arrangements for carrying out the invention.
At first, according to an aspect of the present invention which is directed to a device such as, for example, an IC card, which includes hardware for executing a high-speed algorithm for the residual multiplication arithmetics (hereinafter the hardware will be referred to as the residual multiplier), there is provided an elliptic curve encryption processing method in which arithmetic operations involved in the elliptic curve encryption processing are realized largely by the residual multiplication arithmetics (i.e., modular multiplication on the set of integers) so that the residual multiplier can be utilized effectively.
More specifically, the residual arithmetics performed in succession to generation of random numbers required for the elliptic curve encryption processing and the residual arithmetics involved in the signature generation processing are so structurized as to be capable of being executed by using the residual multiplier. Furthermore, in order to make it possible to utilize effectively the residual multiplier for the elliptic curve arithmetics, the residual division arithmetic (i.e., modular division on the set of integers) involved in the elliptic curve addition arithmetic is transferred into the residual multiplication arithmetic by transforming points on an elliptic curve in the two-dimensional affine coordinate system into those in a three-dimensional coordinate system, wherein the residual multiplication arithmetic is executed by making use of the residual multiplier.
According to another aspect of the present invention which is directed to the scheme for speeding up the multiplicative inverse arithmetic, the multiplicative inverse arithmetics required not only in the coordinate system transformation from the three-dimensional coordinate system to the two-dimensional affine coordinate system but also in generating the signature data are realized by resorting to the residual multiplication arithmetic (i.e., modular multiplication on the set of integers). The multiplicative inverse arithmetic for the residue system is ordinarily realized by making use of algorithm such as extended Euclidean algorithm. However, in the case where modulus to the residue or remainder is prime number, the multiplicative inverse arithmetic can be realized by using only the residual multiplication arithmetic without need for relying on the algorithm such as the extended Euclidean algorithm. This will be elucidated below.
According to the Fermat""s theorem, the statement given by the undermentioned expression can apply valid to a positive integer xcex1 which is relatively prime to a prime number xcex2:
xcex1xcex2xe2x88x921xe2x89xa11 (mod xcex2)
According to this theorem, the multiplicative inverse arithmetic xe2x80x9cxcex1xe2x88x921 mod xcex2xe2x80x9d can be expressed as follows:
xcex1xe2x88x921xe2x89xa1xcex1xcex2xe2x88x922 (mod xcex2)
According to an aspect of the present invention, the values of the order p of a finite field and the order n of a base point are represented by prime numbers of large values, respectively, so that the condition for fulfilling the Fermat""s theorem mentioned above, i.e., the condition that the prime number xcex2 and the positive integer a are relatively prime, can always be satisfied. Accordingly, the value or quantity xcex1xe2x88x921 mod xcex2 is equal to the quantity xcex1xcex2xe2x88x922 mod xcex2. Thus, assuming, by way of example, that the residual multiplication arithmetic is performed by resorting to the binary operation method, the value of multiplicative inverse, i.e., xcex1xe2x88x921 mod xcex2, can be determined by performing the residual multiplication arithmetic by a number of times given by ((|xcex2xe2x88x922|xe2x88x921)xc3x973/2), where |xcex2xe2x88x922| represents bit number of (xcex2xe2x88x922). By adopting the method mentioned above, it is also possible to reduce the program size or scale because of no necessity of preparing the algorithm such as Euclidean algorithm or the like as a program(s).
In an arrangement according to another aspect of the present invention, those parameters which are used very frequently in the arithmetic operations and which can be calculated beforehand with a personal computer or the like are previously determined to be stored as one of system information in a rewritable nonvolatile memory incorporated in the IC card. Thus, computational complexity of the arithmetic processing can be reduced. In this conjunction, as the data to be stored previously in the rewritable nonvolatile memory as the system information, there may be mentioned order p of a finite field, values xe2x80x9caR mod pxe2x80x9d resulting from transformation of elliptic curve parameter a, point (X, Y, Z) which can be obtained by transforming two-dimensional affine coordinates (x, y) of a point P (base point) on the elliptic curve into coordinates in a three-dimensional projective coordinate system, which coordinates are then transformed to be appropriate for a residual multiplication arithmetic unit, order n of the base point, secret key d, values xe2x80x9c2R mod pxe2x80x9d, xe2x80x9c3R mod pxe2x80x9d, xe2x80x9c4R mod pxe2x80x9d, xe2x80x9c8R mod pxe2x80x9d and xe2x80x9c2xe2x88x921R mod pxe2x80x9d resulting from transformation of constants, respectively, which are employed in the elliptic curve arithmetics, and values xe2x80x9cR mod pxe2x80x9d, xe2x80x9cR mod nxe2x80x9d, xe2x80x9cR2 mod pxe2x80x9d and xe2x80x9cR2 mod nxe2x80x9d employed in the residual multiplication arithmetic. In the above description, R represents a positive integer which satisfies the condition that R=2|p|, where |p| represents the bit number of the order p of the finite field.
According to yet another aspect of the present invention, there is provided an IC card in which points corresponding to integer multiples of the base point are stored in a rewritable nonvolatile memory incorporated in the IC card in the form of tables with a view to reducing the computation overhead by decreasing the number of processings involved in the elliptic curve addition arithmetics. In this conjunction, it should be mentioned that the computational overhead can be reduced as the number of the table increases. However, the amount of data (i.e., data size) to be stored in the rewritable nonvolatile memory will then increase correspondingly. Accordingly, it is also taught by the invention that points obtained by exponentiation of the base points by four are stored in the memory in the form of tables. In that case, the number of the points stored as the tables, i.e., the number of tables, is given by |p|/2, where |p| represents the bit number of the order p of the finite field. The tabled values are transformed into coordinates on a three-dimensional projective coordinate system and then transformed to points given by Pi (Xi, Yi, Zi) suited for arithmetics executed by the residual multiplier. In the expression mentioned just above, i represents an integer satisfying the condition that 0xe2x89xa6i less than |p|/2.
In the case where the large memory capacity is available, the points resulting from exponentiation of the base points by two may be stored as tables. In that case, the arithmetic operations on the elliptic curve may be structurized only with the elliptic addition arithmetics, whereby the number of processings as required can be reduced.
In general, when the values of points resulting from 2n (where n represents a natural number) of the base points are stored as tables, the number of the tables is given by |p|/n, where |p| represents the bit number of order p of the finite field. In practical applications, the number of the tables may be determined by taking into account the computation performance of a CPU and the capacity of a memory destined for storing the tables.
Other subjects, features and advantages of the present invention will become apparent from the following detailed description of the embodiments taken in conjunction with the accompanying drawings.